#include <iostream>
#include <boost/format.hpp>

#include <cassert>


#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
#include "portable_timer.h"


using std::priority_queue;
using std::cout;
using std::sort;
using std::nth_element;


class t_ran_locus
{
	
public:
	unsigned beg;
	unsigned end;
	double   score;
	t_ran_locus(unsigned beg_, unsigned end_, double score_):beg(beg_), end(end_), score(score_){}
	~t_ran_locus(){}
	bool operator <(const t_ran_locus& other) const
	{
		return score > other.score;
	}
};
std::ostream& operator << (std::ostream& outstrm, const t_ran_locus& rl)
{
	outstrm << boost::format("[%1$5d, %2$5d : %3$5.2f]\n") % rl.beg % rl.end % rl.score;
//	outstrm
//		<< "[" << rl.beg
//		<< "," << rl.end
//		<< ":" << rl.score
//		<< "]\n";
}
int main (int argc, char *argv[])
{
    double to_random_float = 1.0 / RAND_MAX * 50.0;
	std::priority_queue<t_ran_locus> top_values;

	const unsigned CNT_STORE  =    100000;
	const unsigned CACHE_SIZE =    CNT_STORE * 5;
	const unsigned ITERATIONs = 500000000;


	std::vector<t_ran_locus> top_values_v;
	top_values_v.reserve(CACHE_SIZE);
	t_portable_timer	timer;
	t_portable_timer	total_timer;

	// for (unsigned i = 0; i < ITERATIONs; ++i)
	// {
	// 	auto ri = rand() * to_random_float;
	// 
	// 	//top_values.push(t_ran_locus(i, i + 100, ri));
	// 	//if (top_values.size() > 1000)
	// 	//  top_values.pop();
	// 	top_values_v.push_back(t_ran_locus(i, i + 100, ri));
	// 	if (top_values_v.size() > CACHE_SIZE)
	// 	{
	// 		nth_element(top_values_v.begin(), top_values_v.begin() + CNT_STORE, top_values_v.end());
	// 		top_values_v.erase(top_values_v.begin() + CNT_STORE, top_values_v.end());
	// 	}
	// }
	// std::cerr << std::endl;
	// std::cout << "Looped " << timer.pretty_reset()  << "\n";
	// 
	// if (top_values_v.size() > CNT_STORE)
	// {
	// 	nth_element(top_values_v.begin(), top_values_v.begin() + CNT_STORE, top_values_v.end());
	// 	sort(top_values_v.begin(), top_values_v.end());
	// }
	// cout << std::endl;
	// std::cout << "Done in " << total_timer.pretty_reset()  << "\n";
//	cout << "Popping out elements...";
//	while (!top_values_v.empty())
//	{
//		cout << " " << top_values_v.back();
//		top_values_v.pop_back();
//	}



	//timer.reset();
	//total_timer.reset();
	//
	//for (unsigned i = 0; i < ITERATIONs; ++i)
	//{
	//	auto ri = rand() * to_random_float;
	//
	//	top_values.push(t_ran_locus(i, i + 100, ri));
	//	if (top_values.size() > CNT_STORE)
	//	  top_values.pop();
	//}
	//std::cerr << std::endl;
	//std::cout << "Done " << timer.pretty_reset()  << "\n";


	timer.reset();
	total_timer.reset();

	for (unsigned i = 0; i < ITERATIONs; ++i)
	{
		auto ri = rand() * to_random_float;

		if (top_values.size() > CNT_STORE and top_values.top().score < ri)
		{
			top_values.pop();
			top_values.push(t_ran_locus(i, i + 100, ri));
		}
	}
	std::cerr << std::endl;
	std::cout << "Done " << timer.pretty_reset()  << "\n";

	cout << "Popping out elements...";
	while (!top_values.empty())
	{
		cout << " " << top_values.top();
		top_values.pop();
	}





    return(0);
}






